package Classic150;

public class 买卖股票的最佳时机3 {
    /*
        空间优化，存储两次交易的状态，一天一共就有五个状态，
        0.没有操作 （其实我们也可以不设置这个状态）
        1.第一次持有股票
        2.第一次不持有股票
        3.第二次持有股票
        4.第二次不持有股票
    */
    public int maxProfit(int[] prices) {
        int[] dp = new int[5];
        dp[1] = -prices[0];
        dp[3] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[1] = Math.max(dp[0] - prices[i], dp[1]);
            dp[2] = Math.max(dp[1] + prices[i], dp[2]);
            dp[3] = Math.max(dp[2] - prices[i], dp[3]);
            dp[4] = Math.max(dp[3] + prices[i], dp[4]);
        }
        return dp[4];
    }
}
